package hot100;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    //哈希表、双向链表(哈希表可以实现get,put中查找key的O1时间复杂度)
    //头尾空节点辅助

    //双向链表
    class DoubLinkedNode {
        int key;
        int value;
        DoubLinkedNode prev;
        DoubLinkedNode next;
        public DoubLinkedNode() {}
        public DoubLinkedNode(int key,int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer,DoubLinkedNode> hash = new HashMap<Integer,DoubLinkedNode>();
    private int size;
    private int capacity;
    //头尾节点
    DoubLinkedNode head,end;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DoubLinkedNode();
        end = new DoubLinkedNode();
        head.next = end;
        end.prev = head;

    }

    public int get(int key) {
        //通过哈希表获取到node
        DoubLinkedNode node = hash.get(key);
        if(node == null) {
            return -1;
        }
        //key存在
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DoubLinkedNode node = hash.get(key);
        if(node == null) {
            //node 为空,创建新节点插入
            DoubLinkedNode newNode = new DoubLinkedNode(key,value);
            hash.put(key,newNode);
            //添加到链表头部
            addToHead(newNode);
            ++size;
            if(size > capacity) {
                //超出容量
                DoubLinkedNode temp = removeEnd();
                hash.remove(temp.key);
                --size;
            }
        }else {
            //node 不为空
            node.value = value;
            moveToHead(node);
        }

    }

    //更新使用过的节点到头结点
    public void moveToHead(DoubLinkedNode node) {
        //拔除node节点
        removeNode(node);
        //插入到头结点之前
        addToHead(node);
    }

    //拔除node节点
    public void removeNode(DoubLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    //插入到头结点之前
    public void addToHead(DoubLinkedNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    //淘汰最久未使用节点
    public DoubLinkedNode removeEnd() {
        DoubLinkedNode node = end.prev;
        removeNode(node);
        return node;
    }
}
